package com.vladium.utils;

import java.lang.reflect.Array;
import java.lang.reflect.Field;
import java.lang.reflect.Modifier;
import java.security.AccessController;
import java.security.PrivilegedActionException;
import java.security.PrivilegedExceptionAction;
import java.util.*;

// ----------------------------------------------------------------------------
/**
 * This non-instantiable class presents an API for object sizing and profiling
 * as described in the article. See individual methods for details.
 * <P>
 * This implementation is J2SE 1.4+ only. You would need to code your own
 * identity hashmap to port this to earlier Java versions.
 * <P>
 * Security: this implementation uses AccessController.doPrivileged() so it
 * could be granted privileges to access non-public class fields separately from
 * your main application code. The minimum set of persmissions necessary for
 * this class to function correctly follows:
 * 
 * <pre>
 *      permission java.lang.RuntimePermission &quot;accessDeclaredMembers&quot;;
 *      permission java.lang.reflect.ReflectPermission &quot;suppressAccessChecks&quot;;
 * </pre>
 * 
 * @see IObjectProfileNode
 * @author (C) <a
 *         href="http://www.javaworld.com/columns/jw-qna-index.shtml">Vlad
 *         Roubtsov</a>, 2003
 */
public abstract class ObjectProfiler
{
	// public: ................................................................
	// the following constants are physical sizes (in bytes) and are
	// JVM-dependent:
	// [the current values are Ok for most 32-bit JVMs]
	public static final int OBJECT_SHELL_SIZE = 8; // java.lang.Object shell
	// size in bytes
	public static final int OBJREF_SIZE = 4;
	public static final int LONG_FIELD_SIZE = 8;
	public static final int INT_FIELD_SIZE = 4;
	public static final int SHORT_FIELD_SIZE = 2;
	public static final int CHAR_FIELD_SIZE = 2;
	public static final int BYTE_FIELD_SIZE = 1;
	public static final int BOOLEAN_FIELD_SIZE = 1;
	public static final int DOUBLE_FIELD_SIZE = 8;
	public static final int FLOAT_FIELD_SIZE = 4;
	/**
	 * Set this to 'true' to make the node names default to using class names
	 * without package prefixing for more compact dumps
	 */
	public static final boolean SHORT_TYPE_NAMES = false;
	/**
	 * If this is 'true', node names will use short class names for common
	 * classes in java.lang.* and java.util.*, regardless of
	 * {@link #SHORT_TYPE_NAMES} setting.
	 */
	public static final boolean SHORT_COMMON_TYPE_NAMES = true;

	/**
	 * Estimates the full size of the object graph rooted at 'obj'. Duplicate
	 * data instances are correctly accounted for. The implementation is not
	 * recursive.
	 * <P>
	 * Invariant: sizeof(obj) == profile(obj).size() if 'obj' is not null
	 * 
	 * @param obj
	 *        input object instance to be measured
	 * @return 'obj' size [0 if 'obj' is null']
	 */
	public static int sizeof( final Object obj )
	{
		if( obj == null )
			return 0;
		final IdentityHashMap visited = new IdentityHashMap();
		return computeSizeof( obj, visited, CLASS_METADATA_CACHE );
	}

	/**
	 * Estimates the full size of the object graph rooted at 'obj' by
	 * pre-populating the "visited" set with the object graph rooted at 'base'.
	 * The net effect is to compute the size of 'obj' by summing over all
	 * instance data contained in 'obj' but not in 'base'.
	 * 
	 * @param base
	 *        graph boundary [may not be null]
	 * @param obj
	 *        input object instance to be measured
	 * @return 'obj' size [0 if 'obj' is null']
	 */
	public static int sizedelta( final Object base, final Object obj )
	{
		if( obj == null )
			return 0;
		if( base == null )
			throw new IllegalArgumentException( "null input: base" );
		final IdentityHashMap visited = new IdentityHashMap();
		computeSizeof( base, visited, CLASS_METADATA_CACHE );
		return visited.containsKey( obj ) ? 0 : computeSizeof( obj, visited, CLASS_METADATA_CACHE );
	}

	/**
	 * Creates a spanning tree representation for instance data contained in
	 * 'obj'. The tree is produced using bread-first traversal over the full
	 * object graph implied by non-null instance and array references
	 * originating in 'obj'.
	 * 
	 * @see IObjectProfileNode
	 * @param obj
	 *        input object instance to be profiled [may not be null]
	 * @return the profile tree root node [never null]
	 */
	public static IObjectProfileNode profile( final Object obj )
	{
		if( obj == null )
			throw new IllegalArgumentException( "null input: obj" );
		final IdentityHashMap visited = new IdentityHashMap();
		final ObjectProfileNode root = createProfileTree( obj, visited, CLASS_METADATA_CACHE );
		finishProfileTree( root );
		return root;
	}

	// convenience methods:
	public static String pathName( final IObjectProfileNode[] path )
	{
		final StringBuffer s = new StringBuffer();
		for( int i = 0; i < path.length; ++i )
		{
			if( i != 0 )
				s.append( '/' );
			s.append( path[i].name() );
		}
		return s.toString();
	}

	static final String INPUT_OBJECT_NAME = "<INPUT>"; // root node name

	// private: ...............................................................
	/*
	 * Internal class used to cache class metadata information.
	 */
	private static final class ClassMetadata
	{
		ClassMetadata( final int primitiveFieldCount, final int shellSize, final Field[] refFields )
		{
			m_primitiveFieldCount = primitiveFieldCount;
			m_shellSize = shellSize;
			m_refFields = refFields;
		}

		// all fields are inclusive of superclasses:
		final int m_primitiveFieldCount;
		final int m_shellSize; // class shell size
		final Field[] m_refFields; // cached non-static fields (made accessible)
	} // end of nested class

	private static final class ClassAccessPrivilegedAction implements
			PrivilegedExceptionAction<Field[]>
	{
		public Field[] run() throws Exception
		{
			return m_cls.getDeclaredFields();
		}

		void setContext( final Class<?> cls )
		{
			m_cls = cls;
		}

		private Class<?> m_cls;
	} // end of nested class

	private static final class FieldAccessPrivilegedAction implements
			PrivilegedExceptionAction<Void>
	{
		public Void run() throws Exception
		{
			m_field.setAccessible( true );
			return null;
		}

		void setContext( final Field field )
		{
			m_field = field;
		}

		private Field m_field;
	} // end of nested class

	private ObjectProfiler()
	{} // this class is not extendible

	/*
	 * The main worker method for sizeof() and sizedelta().
	 */
	private static int computeSizeof( Object obj, final IdentityHashMap visited,
		final Map /* Class->ClassMetadata */metadataMap )
	{
		// this uses depth-first traversal; the exact graph traversal algorithm
		// does not matter for computing the total size and this method could be
		// easily adjusted to do breadth-first instead (addLast() instead of
		// addFirst()),
		// however, dfs/bfs require max queue length to be the length of the
		// longest
		// graph path/width of traversal front correspondingly, so I expect
		// dfs to use fewer resources than bfs for most Java objects;
		if( obj == null )
			return 0;
		final LinkedList queue = new LinkedList();
		visited.put( obj, obj );
		queue.add( obj );
		int result = 0;
		final ClassAccessPrivilegedAction caAction = new ClassAccessPrivilegedAction();
		final FieldAccessPrivilegedAction faAction = new FieldAccessPrivilegedAction();
		while( !queue.isEmpty() )
		{
			obj = queue.removeFirst();
			final Class objClass = obj.getClass();
			if( objClass.isArray() )
			{
				final int arrayLength = Array.getLength( obj );
				final Class componentType = objClass.getComponentType();
				result += sizeofArrayShell( arrayLength, componentType );
				if( !componentType.isPrimitive() )
				{
					// traverse each array slot:
					for( int i = 0; i < arrayLength; ++i )
					{
						final Object ref = Array.get( obj, i );
						if( (ref != null) && !visited.containsKey( ref ) )
						{
							visited.put( ref, ref );
							queue.addFirst( ref );
						}
					}
				}
			}
			else
			// the object is of a non-array type
			{
				final ClassMetadata metadata = getClassMetadata( objClass, metadataMap, caAction,
					faAction );
				final Field[] fields = metadata.m_refFields;
				result += metadata.m_shellSize;
				// traverse all non-null ref fields:
				for( int f = 0, fLimit = fields.length; f < fLimit; ++f )
				{
					final Field field = fields[f];
					final Object ref;
					try
					// to get the field value:
					{
						ref = field.get( obj );
					}
					catch( Exception e )
					{
						throw new RuntimeException( "cannot get field [" + field.getName()
								+ "] of class [" + field.getDeclaringClass().getName() + "]: "
								+ e.toString() );
					}
					if( (ref != null) && !visited.containsKey( ref ) )
					{
						visited.put( ref, ref );
						queue.addFirst( ref );
					}
				}
			}
		}
		return result;
	}

	/*
	 * Performs phase 1 of profile creation: bread-first traversal and node
	 * creation.
	 */
	private static ObjectProfileNode createProfileTree( Object obj, final IdentityHashMap visited,
		final Map /* Class->ClassMetadata */metadataMap )
	{
		final ObjectProfileNode root = new ObjectProfileNode( null, obj, null );
		root.m_modifiers = Modifier.PUBLIC;
		LinkedList<ObjectProfileNode> queue = new LinkedList<ObjectProfileNode>();
		queue.addFirst( root );
		visited.put( obj, root );
		final ClassAccessPrivilegedAction caAction = new ClassAccessPrivilegedAction();
		final FieldAccessPrivilegedAction faAction = new FieldAccessPrivilegedAction();
		while( !queue.isEmpty() )
		{
			final ObjectProfileNode node = queue.removeFirst();
			obj = node.m_obj;
			final Class<?> objClass = obj.getClass();
			if( objClass.isArray() )
			{
				int arrayLength = Array.getLength( obj );
				Class<?> componentType = objClass.getComponentType();
				// add shell pseudo-node:
				final AbstractShellProfileNode shell = new ArrayShellProfileNode( node, objClass,
					arrayLength );
				shell.m_size = sizeofArrayShell( arrayLength, componentType );
				shell.m_modifiers = node.m_modifiers;
				node.m_shell = shell;
				node.addFieldRef( shell );
				if( !componentType.isPrimitive() )
				{
					// traverse each array slot:
					for( int i = 0; i < arrayLength; ++i )
					{
						final Object ref = Array.get( obj, i );
						if( ref != null )
						{
							ObjectProfileNode child = (ObjectProfileNode) visited.get( ref );
							if( child != null )
								++child.m_refcount;
							else
							{
								child = new ObjectProfileNode( node, ref, new ArrayIndexLink(
									node.m_link, i ) );
								node.addFieldRef( child );
								queue.addLast( child );
								visited.put( ref, child );
							}
						}
					}
				}
			}
			else
			// the object is of a non-array type
			{
				final ClassMetadata metadata = getClassMetadata( objClass, metadataMap, caAction,
					faAction );
				final Field[] fields = metadata.m_refFields;
				// add shell pseudo-node:
				final AbstractShellProfileNode shell = new ObjectShellProfileNode( node,
					metadata.m_primitiveFieldCount, metadata.m_refFields.length );
				shell.m_size = metadata.m_shellSize;
				node.m_shell = shell;
				node.addFieldRef( shell );
				// traverse all non-null ref fields:
				for( int f = 0, fLimit = fields.length; f < fLimit; ++f )
				{
					final Field field = fields[f];
					final Object ref;
					try
					// to get the field value:
					{
						ref = field.get( obj );
					}
					catch( Exception e )
					{
						throw new RuntimeException( "cannot get field [" + field.getName()
								+ "] of class [" + field.getDeclaringClass().getName() + "]: "
								+ e.toString() );
					}
					if( ref != null )
					{
						ObjectProfileNode child = (ObjectProfileNode) visited.get( ref );
						if( child != null )
							++child.m_refcount;
						else
						{
							child = new ObjectProfileNode( node, ref, new ClassFieldLink( field ) );
							child.m_modifiers = field.getModifiers();
							node.addFieldRef( child );
							queue.addLast( child );
							visited.put( ref, child );
						}
					}
				}
			}
		}
		return root;
	}

	/*
	 * Performs phase 2 of profile creation: totalling of node sizes (via
	 * non-recursive post-order traversal of the tree created in phase 1) and
	 * 'locking down' of profile nodes into their most compact form.
	 */
	private static void finishProfileTree( ObjectProfileNode node )
	{
		final LinkedList queue = new LinkedList();
		IObjectProfileNode lastFinished = null;
		while( node != null )
		{
			// note that an unfinished non-shell node has its child count
			// in m_size and m_children[0] is its shell node:
			if( (node.m_size == 1) || (lastFinished == node.m_children[1]) )
			{
				node.finish();
				lastFinished = node;
			}
			else
			{
				queue.addFirst( node );
				for( int i = 1; i < node.m_size; ++i )
				{
					final IObjectProfileNode child = node.m_children[i];
					queue.addFirst( child );
				}
			}
			if( queue.isEmpty() )
				return;
			else
				node = (ObjectProfileNode) queue.removeFirst();
		}
	}

	/*
	 * A helper method for manipulating a class metadata cache.
	 */
	private static ClassMetadata getClassMetadata( final Class<?> cls, final Map /*
																				 * Class-
																				 * >
																				 * ClassMetadata
																				 */metadataMap,
		final ClassAccessPrivilegedAction caAction, final FieldAccessPrivilegedAction faAction )
	{
		if( cls == null )
			return null;
		ClassMetadata result;
		synchronized( metadataMap )
		{
			result = (ClassMetadata) metadataMap.get( cls );
		}
		if( result != null )
			return result;
		int primitiveFieldCount = 0;
		int shellSize = OBJECT_SHELL_SIZE; // java.lang.Object shell
		final List /* Field */refFields = new LinkedList();
		final Field[] declaredFields;
		try
		{
			caAction.setContext( cls );
			declaredFields = (Field[]) AccessController.doPrivileged( caAction );
		}
		catch( PrivilegedActionException pae )
		{
			throw new RuntimeException( "could not access declared fields of class "
					+ cls.getName() + ": " + pae.getException() );
		}
		for( int f = 0; f < declaredFields.length; ++f )
		{
			final Field field = declaredFields[f];
			if( (Modifier.STATIC & field.getModifiers()) != 0 )
				continue;
			final Class<?> fieldType = field.getType();
			if( fieldType.isPrimitive() )
			{
				// memory alignment ignored:
				shellSize += sizeofPrimitiveType( fieldType );
				++primitiveFieldCount;
			}
			else
			{
				// prepare for graph traversal later:
				if( !field.isAccessible() )
				{
					try
					{
						faAction.setContext( field );
						AccessController.doPrivileged( faAction );
					}
					catch( PrivilegedActionException pae )
					{
						throw new RuntimeException( "could not make field " + field
								+ " accessible: " + pae.getException() );
					}
				}
				// memory alignment ignored:
				shellSize += OBJREF_SIZE;
				refFields.add( field );
			}
		}
		// recurse into superclass:
		final ClassMetadata superMetadata = getClassMetadata( cls.getSuperclass(), metadataMap,
			caAction, faAction );
		if( superMetadata != null )
		{
			primitiveFieldCount += superMetadata.m_primitiveFieldCount;
			shellSize += superMetadata.m_shellSize - OBJECT_SHELL_SIZE;
			refFields.addAll( Arrays.asList( superMetadata.m_refFields ) );
		}
		final Field[] _refFields = new Field[refFields.size()];
		refFields.toArray( _refFields );
		result = new ClassMetadata( primitiveFieldCount, shellSize, _refFields );
		synchronized( metadataMap )
		{
			metadataMap.put( cls, result );
		}
		return result;
	}

	/*
	 * Computes the "shallow" size of an array instance.
	 */
	private static int sizeofArrayShell( final int length, final Class componentType )
	{
		// this ignores memory alignment issues by design:
		final int slotSize = componentType.isPrimitive() ? sizeofPrimitiveType( componentType )
				: OBJREF_SIZE;
		return OBJECT_SHELL_SIZE + INT_FIELD_SIZE + OBJREF_SIZE + length * slotSize;
	}

	/*
	 * Returns the JVM-specific size of a primitive type.
	 */
	private static int sizeofPrimitiveType( final Class type )
	{
		if( type == int.class )
			return INT_FIELD_SIZE;
		else if( type == long.class )
			return LONG_FIELD_SIZE;
		else if( type == short.class )
			return SHORT_FIELD_SIZE;
		else if( type == byte.class )
			return BYTE_FIELD_SIZE;
		else if( type == boolean.class )
			return BOOLEAN_FIELD_SIZE;
		else if( type == char.class )
			return CHAR_FIELD_SIZE;
		else if( type == double.class )
			return DOUBLE_FIELD_SIZE;
		else if( type == float.class )
			return FLOAT_FIELD_SIZE;
		else
			throw new IllegalArgumentException( "not primitive: " + type );
	}

	// class metadata cache:
	private static final Map CLASS_METADATA_CACHE = new WeakHashMap( 101 );
} // end of class
// ----------------------------------------------------------------------------
